616F - Expensive Strings - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define N 600004
#define ll long long
#define db long double
using namespace __gnu_pbds;
using namespace std;
string s;
struct suf { int vt,w[2]; };
suf p[N],tam[N];
int n,i,j,sh[N],nx[N],vt[N],pos[N][22],k,u,gh[N],ts[26],lcp[N];
bool cmp(suf a,suf b) { return s[a.vt]<s[b.vt]; }
void Suffix_sort()
{
    sort(p+1,p+n+1,cmp);
    int cnt=0,bc=0;
    for(i=1;i<=n;i++)
    {
        if(i==1 || cmp(p[i-1],p[i])) cnt++;
        pos[p[i].vt][0]=cnt;
    }
    for(int step=1;(1<<(step-1))<=n;step++)
    {
        for(i=1;i<=n;i++)
        {
            p[i].w[0]=pos[p[i].vt][step-1];
            if(p[i].vt+(1<<(step-1))>n) p[i].w[1]=0;
            else p[i].w[1]=pos[p[i].vt+(1<<(step-1))][step-1];
        }
        for(int k=1;k>=0;k--)
        {
            bc++;
            for(i=n;i>=1;i--)
            {
                if(sh[p[i].w[k]]<bc)
                {
                    sh[p[i].w[k]]=bc; nx[i]=0;
                }
                else nx[i]=vt[p[i].w[k]];
                vt[p[i].w[k]]=i;
            }
            int cnt=0;
            for(i=0;i<=n;i++)
            {
                if(sh[i]<bc) continue;
                for(j=vt[i];j>0;j=nx[j]) tam[++cnt]=p[j];
            }
            swap(p,tam);
        }
        int cnt=0;
        for(i=1;i<=n;i++)
        {
            if(i==1 || p[i].w[0]!=p[i-1].w[0] || p[i].w[1]!=p[i-1].w[1]) cnt++;
            pos[p[i].vt][step]=cnt;
        }
    }
}
int same(int i,int j)
{
    int u=i-1,v=j-1,lg=trunc(log2(n))+1,k;
    for(k=lg;k>=0;k--)
        if(u+(1<<k)<=gh[i] && v+(1<<k)<=gh[j] && pos[u+1][k]==pos[v+1][k])
        {
            u+=(1<<k);
            v+=(1<<k);
        }
    return u-i+1;
}
vector <pair <int,int> > vec[N];
int r[N];
long long sum[N],c[N],kq;
int root(int u)
{
    if(u==r[u]) return u;
    return r[u]=root(r[u]);
}
int main()
{
   // freopen("ntu.inp","r",stdin);
   // freopen("ntu.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n; s=" ";
    for(i=1;i<=n;i++)
    {
        string x;
        cin>>x; s+=x; s+="$";
    }
    j=1;
    for(i=1;i<=n;i++)
    {
        cin>>k;
        while(s[j]!='$') c[j++]=k;
        j++;
    }
    n=s.length()-1;
    for(i=n;i>=1;i--)
    {
        if(s[i]=='$') gh[i]=i-1; else gh[i]=gh[i+1];
    }
    for(i=1;i<=n;i++) p[i]={ i,0,0 };
    Suffix_sort();
    for(u=1;u<=n;u++) { r[u]=u; sum[u]=c[p[u].vt]; }
    for(i=1;i<=n;i++)
    {
        lcp[i]=same(p[i].vt,p[i-1].vt);
        vec[lcp[i]].push_back({ i,i-1 });
    }
    for(i=1;i<=n;i++)
        if(max(lcp[i],lcp[i+1])<gh[p[i].vt]-p[i].vt+1) kq=max(kq,(gh[p[i].vt]-p[i].vt+1)*c[p[i].vt]);
    for(i=n;i>=1;i--)
    {
        vector <int> luu;
        while(vec[i].size()>0)
        {
            int u=root(vec[i].back().first),v=root(vec[i].back().second);
            vec[i].pop_back();
            if(u!=v)
            {
                r[v]=u;
                sum[u]+=sum[v];
                luu.push_back(u);
            }
        }
        while(luu.size()>0)
        {
            int u=root(luu.back()); luu.pop_back();
            kq=max(kq,i*sum[u]);
        }
    }
    cout<<kq;
}